The present invention relates to multicasting in a data processing network and, more particularly, to a method and apparatus for banked multicast common memory switches for use in an asynchronous transfer mode (ATM) network.
ATM networks pass data in the form of cells. The cells, which are of fixed size, pass through one or more switches on the way to a specified destination which may be another switch, a terminal, or some other component in the network. An individual cell may need to be sent to several different destinations in the network from a single switch.
For purposes of this discussion, the term "multicasting" refers to the distribution of a cell to multiple destinations. When multicast, an individual cell is copied in a switch, and the copies are sent to multiple destinations from the switch. In a common memory switch, the cell copying operation can be efficiently achieved by storing the cell in memory and generating multiple copies of the cell memory location (the cell address). Each copy of the cell address is stored at an output queue of the switch. A count of the number of copies of the cell made and transmitted is stored in a count memory. As copies of the cell exit the switch, the count memory is decremented. When the last cell copy is issued, the count memory is reduced to zero ("0"). At this point the address can be reused for another cell and is returned to a list of free memory locations.
Referring now to FIG. 1, there is shown a block diagram of common memory switch 100 capable of performing multicasting. As shown, switch 100 includes a data store 102, which acts as a central buffer where incoming cells 104 are stored. Common memory switch 100 also contains a multicast count memory 106, which may be used to keep track of the number of copies of the cell produced for purposes of maintaining a list of free memory address spaces in the data store 102.
Known multicast cell counting implementations use a single memory to count the cell copies exiting the memory switch. FIG. 2 is useful for discussing the single memory multicast count implementation. This implementation requires several memory operations to track cell copies. The cell count value is written to the memory on enqueue, i.e., when a cell enters the switch (step 200). When the cell leaves the switch, the cell count value is read (step 202) from the multicast count memory and decremented (step 204). The decremented count value is then written to and stored in the multicast count memory (step 206). A cell count value of zero indicates all cell copies have been transmitted from the switch to the intended destinations.
This approach thus requires three memory accesses on the memory per cell cycle. For purposes of this discussion, a cell "cycle" is the enqueuing of a single cell to a switch and the subsequent dequeuing of that cell from the switch. Since three memory accesses are performed for each cell arrival, the memory must function generally three times as fast as the cell arrival rate. This performance requirement for the memory greatly limits the types of memory that can successfully perform the task of multicast counting in common memory switches. Generally, only small, fast memories are capable of supporting multicasting. This limits the capacity of the switch or restricts the number of memory locations that can be used for multicast cells, as the multicast counting operation is the most demanding (in terms of memory bandwidth) in a common memory switch.
It is, therefore, desirable to provide a method and apparatus for multicasting incorporating a cell counting strategy having a reduced number of per-memory accesses. Such a method and apparatus for multicasting would in turn feature a memory capable of operating at a reduced speed relative to the cell arrival rate compared to existing implementations, broadening the variety of memories available for performing multicast cell counting. The ability to use a wider variety of memories yields cost savings and allows higher capacity switches to be built.